package main

/**
使用go语言实现算法链表是否有环

该算法使用快慢指针的方式，如果链表有环，那么快指针一定会追上慢指针。
如果链表没有环，那么快指针最终会指向 null，退出循环。

*/

type ListNode struct {
	Val  int
	Next *ListNode
}

func hasCycle(head *ListNode) bool {

	if head == nil || head.Next == nil {
		return false
	}

	slow := head
	fast := head.Next

	for slow != fast {
		if fast == nil || fast.Next == nil {
			return false
		}
		slow = slow.Next
		fast = fast.Next.Next
	}
	return true
}

type ListNode4 struct {
	Val  int
	Next *ListNode4
}

func hasCycle2(head *ListNode2) bool {

	if head.Next == nil || head == nil {
		return false
	}

	var fast = head.Next
	var slow = head
	for slow != fast {

		if slow.Next == nil || fast.Next == nil {
			return false
		}
		fast = fast.Next.Next
		slow = slow.Next
	}
	return true
}

func hasCycle3(node4 *ListNode4) bool {

	m := make(map[*ListNode4]struct{})
	for node4 != nil {
		if _, ok := m[node4]; ok {
			return true
		}
		m[node4] = struct{}{}
		node4 = node4.Next
	}
	return false
}
